#include <complex>
#include <vector>

const double PI = std::acos(-1);

using Complex = std::complex<double>;

void butterfly(std::vector<Complex>& A)
{
	int n = A.size();
	int h = n >> 1;

	for (int step = 2; step <= n; step <<= 1) {
		for (int i = 0; i < n; i += step) {
			for (int j = i, k = 0; j < i + h; ++j, ++k) {
				Complex u = A[j];
				Complex v = A[j + h] * std::polar(1.0, -2 * PI * k / step);
				A[j] = u + v;
				A[j + h] = u - v;
			}
		}
		h >>= 1;
	}
}

void fft(std::vector<Complex>& A)
{
	int n = A.size();
	int p = 0;
	while ((1 << p) < n) {
		p++;
	}
	std::vector<int> rev(n);

	rev[0] = 0;
	for (int i = 1; i < n; ++i) {
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (p - 1));
	}

	std::vector<Complex> B(n);
	for (int i = 0; i < n; ++i) {
		B[i] = A[rev[i]];
	}

	for (int step = 2; step <= n; step <<= 1) {
		int half = step >> 1;
		Complex wn = std::polar(1.0, -2 * PI / step);

		for (int i = 0; i < n; i += step) {
			Complex w(1);

			for (int j = i; j < i + half; ++j) {
				Complex u = B[j];
				Complex v = w * B[j + half];

				B[j] = u + v;
				B[j + half] = u - v;

				w *= wn;
			}
		}
	}

	A = std::move(B);
}
//创建一个 std::vector<Complex> 对象，并填充它与您想要进行变换的数据。
//
//调用 fft 函数，传入您创建的向量作为参数。
//
//变换后的结果将存储在原始向量中，您可以根据需要进一步处理或分析结果。
//
//请注意，示例代码中使用 std::complex<double> 表示复数，采用了 C++ 标准库提供的复数类。您可以根据自己的需求进行适当的更改。同时，为了获得更高的精度和性能，也可以使用其他的 FFT 库或优化技术。

